import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;

        B.left = D;
        B.right = E;

        C.left = F;
        C.right = G;

        E.right = H;

        return A;
    }
    /**
     * 判断一棵树是否为完全二叉树
     */
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur == null) {
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while(queue.poll() == null && !queue.isEmpty()) {
            ;
        }
        if(queue.isEmpty()) {
            return true;
        }
        return false;
    }
    /**
     * 二叉树最近的公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null) {//两侧
            return root;
        }else if(left != null){
            return left;
        }else {
            return right;
        }
    }
    /**
     * 查找路线
     *      1.判断是否为空
     *      2.判断root是否为node
     *      3.判断左右子树
     */
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flagLeft = getPath(root.left,node,stack);
        if(flagLeft) {
            return true;
        }
        boolean flagRight = getPath(root.right,node,stack);
        if(flagRight) {//为真,证明为node
            return true;
        }
        //都为假,证明路径错误,出栈元素
        stack.pop();
        return false;
    }

    /**
     * 求最近的公共祖先,使用栈
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        int size = 0;
        if(size1 > size2 ) {
            size = size1 - size2;
            while(size != 0) {
                stack1.pop();
                size--;
            }
        }else {
            size = size2 - size1;
            while(size != 0) {
                stack2.pop();
                size--;
            }
        }

        TreeNode tmp = null;
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
            tmp = stack1.pop();
            if(tmp == stack2.pop()) {
                return tmp;
            }
        }
        return null;
    }
    /**
     * 从前序与中序遍历序列构造二叉树
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length - 1);
    }

    public int i;
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode((char)preorder[i]);//创建头节点

        //查找前序遍历i位置节点
        int index = findIIndex(preorder[i],inorder,inBegin,inEnd);
        i++;
        //递归左右子树
        root.left = buildTreeChild(preorder,inorder,inBegin,index - 1);
        root.right = buildTreeChild(preorder,inorder,index + 1,inEnd);

        return root;
    }

    private int findIIndex(int key,int[] inorder,int inBegin,int inEnd) {
        for(int i = inBegin;i <= inEnd;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从中序与后序遍历序列构建二叉树
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        return buildTreeChild(inorder,postorder,0,inorder.length - 1);
    }
    public int a;
    private TreeNode buildTreeChild2(int[] inorder,int[] postorder,int inBegin,int inEnd) {
        int i = postorder.length - 1 - a;
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode((char)postorder[i]);//创建头节点

        //查找后序遍历i位置节点
        int index = findIIndex(postorder[i],inorder,inBegin,inEnd);
        i--;
        a++;
        //递归左右子树
        root.right = buildTreeChild(inorder,postorder,index + 1,inEnd);
        root.left = buildTreeChild(inorder,postorder,inBegin,index - 1);

        return root;
    }

    private int findIIndex2(int key,int[] inorder,int inBegin,int inEnd) {
        for(int i = inBegin;i <= inEnd;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
